package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class PSeven29我的日程安排表I {
//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 方法一：对于两个区间[s1,e1),[s2,e2)，有交集：s1<e2&&s2<e1
     * O(n^2) O(n)
     */
    class MyCalendar {

        List<int[]> booked;

        public MyCalendar() {
            booked = new ArrayList<int[]>();
        }

        public boolean book(int start, int end) {
            for (int[] arr : booked) {
                int l = arr[0], r = arr[1];
                if (l < end && start < r) {
                    return false;
                }
            }
            booked.add(new int[]{start, end});
            return true;
        }
    }
/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * 方法二：二分查找
     * 用TreeSet，对于给定的区间[start,end)，我们查找起点大于等于end的第一个区间[l1，r1)
     * 再查找紧挨着[l1，r1)的前一个区间[l2,r2)
     * 满足：r2<=start<end<=l1，则可预订该区间
     * O(nlogn) n代表日程安排数量，logn排序
     * O(n) n日程安排数据量
     */
    class MyCalendar2 {

        TreeSet<int[]> booked;

        public MyCalendar2() {
            booked = new TreeSet<int[]>((a, b) -> a[0] - b[0]);
        }

        public boolean book(int start, int end) {
            if (booked.isEmpty()) {
                booked.add(new int[]{start, end});
                return true;
            }
            int[] tmp = {end, 0};
            int[] arr = booked.ceiling(tmp);// 找到比end大一点的arr
            // 如果arr是空，说明[start,end)这个区间后面没人了，那么他的前面就取集合最后一个
            // 如果arr不空，后面有，那么前面就取arr的小一点点的区间即前一个区间
            // set:10,20   插入15，25，那么arr就是空，pre就取set最后一个就是10，20
            // set:4，15 20,30 插入1，5，那么arr就是20，30，pre就取比arr小一点的4，15
            int[] prev = arr == null ? booked.last() : booked.lower(arr);
            // 如果arr就是第一个，那么待插入区间前面没人了，那么直接插入到前面
            // 否则，前面有区间，那么插入之前还要比一下前面的区间的右边
            if (arr == booked.first() || booked.lower(tmp)[1] <= start) {
                booked.add(new int[]{start, end});
                return true;
            }
            return false;
        }
    }

    /**
     * 方法二：线段树
     * 预定某个区间，就把某个区间懒标记为该树的下标
     * 我们【假】定义一个超大的数组用作存储树：arr[0,10^9],0不用，为啥，因为这样左子节点就可以表示2n
     * O(nlogC) n日程安排数量，线段树最大深度为logC，C取固定值10^9，查询一次logC，更新一次也是logC，所以book是logC+logC还是logC
     * O(nlogC) 动态线段树，每次预定最多会在线段树上增加logC个节点
     */
    class MyCalendar3 {

        Set<Integer> tree; // 一棵树部分被标记也要入这个集合
        Set<Integer> lazy;// 一棵树整个被标记才入这个集合

        public MyCalendar3() {
            tree = new HashSet<>();
            lazy = new HashSet<>();
        }

        public boolean book(int start, int end) {
            if(query(start,end,0,10^9,1)){
                return false;
            }
            update(start,end,0,10^9,1);
            return true;
        }
        // 在区间l r上，找start，end是否被标记，idx代表树的下标，idx的左节点为2*idx
        // 查找方式：查找是否有懒标记
        public boolean query(int start, int end, int l, int r, int idx) {
            // 待查区间和总区间不想交
            if(start>r||end<l) return false;
            // 该树整颗被标记，用lazy，直接返回true
            if(lazy.contains(idx)) return  true;
            // 该树部分被标记，用tree，也返回true
            if(start<=l&&r<=end) {
                return tree.contains(idx);
            } else{
                int mid = (l+r)>>1;
                // 待查区间和总区间左交
                if(end<=mid){
                    return query(start, end, l, mid, 2*idx);
                }else if(start>mid){// 待查区间和总区间右交
                    return query(start,end,mid+1,r,2*idx+1);
                }else {// 待查区间和总区间中交
                    return query(start,end,l,mid,2*idx) | query(mid+1,end,mid+1,r,2*idx+1);
                }
            }
        }

        // 在区间l r上，更新start，end为已预定，idx代表树的下标，idx的左节点为2*idx
        // 更新方式：懒标记
        public void update(int start, int end, int l, int r, int idx) {
            if(start>r||end<l) return;
            if(start<=l&&r<=end) {
                tree.add(idx);
                lazy.add(idx);
            } else{
                int mid = (l+r)>>1;
                // 待查区间和总区间左交
                if(end<=mid){
                    update(start, end, l, mid, 2*idx);
                }else if(start>mid){// 待查区间和总区间右交
                    update(start,end,mid+1,r,2*idx+1);
                }else {// 待查区间和总区间中交
                    update(start,end,l,mid,2*idx);
                    update(mid+1,end,mid+1,r,2*idx+1);
                }
                tree.add(idx); // 因为在这个else里，该树属于部分被标记，所以只用给tree赋值
            }
        }
    }

    public static void main(String[] args) {
        MyCalendar solution = new PSeven29我的日程安排表I().new MyCalendar();
    }
}